package sysu.el.graph.tree;

import java.util.Arrays;

import sysu.el.graph.GraphConstants;


/**
 * Children Design is not efficient enough due to the traverse of all of the children is
 * time costing comparing to the array in the adjacent list design.
 * However, I just cannot resist the elegance of this data structure design.
 * If it really becomes the bottleneck of the algorithm, I will suggest use the adjacent
 * list design.
 * @author Edwin Lee
 *
 */

public class ChildrenTreeTopo {
	public int root;
	public int children[];
	public int siblings[];
	public int getNodeNum(){
		return children.length;
	}
	
	public ChildrenTreeTopo(int n){
		children = new int[n];
		siblings = new int[n];
//		Arrays.fill(children, GraphConstants.NULL_NODE);
		for (int i=0; i<n; i++){
			children[i] = GraphConstants.NULL_NODE;
			siblings[i] = GraphConstants.NULL_NODE;
		}
	}
	
	protected ChildrenTreeTopo(){
	}
	
	public void addEdge(int fa, int child){
		if (children[fa] == GraphConstants.NULL_NODE){
			children[fa] = child;
		}else{
			int sibling = children[fa];
			while (siblings[sibling] != GraphConstants.NULL_NODE){
				sibling = siblings[sibling];
			}
			siblings[sibling] = child;
		}
	}
	
}
